package q84_largestRectangleArea;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 soluion = new Solution_1();
    }

    /**
     * 这种方法就是每一个柱子都向着两侧扩散，直到找到最大值
     * 这种方法会超时
     */
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }

        int res = 0;
        // 每个柱子都能够向两侧拓展找到最大勾勒的矩形面积
        for (int i = 0; i < heights.length; i++) {

            // 找左边最后 1 个大于等于 heights[i] 的下标
            int left = i;
            int curHeight = heights[i];
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }

            // 找右边最后 1 个大于等于 heights[i] 的索引
            int right = i;
            while (right < heights.length - 1 && heights[right + 1] >= curHeight) {
                right++;
            }

            int width = right - left + 1;
            res = Math.max(res, width * curHeight);
        }

        return res;
    }
}
